package com.hspedu.newData.dmsxl.动态规划.股票问题;
/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-27 
 * @Version: 1.0
 */

public class LC188买卖股票的最佳时机Ⅲ {

    public int maxProfit(int k, int[] prices) {

        int len = prices.length;

        if (len < 2) return 0;

        int[][] dp = new int[len][2*k + 1];

        // 定义所有奇数项是买入，偶数项是卖出

        for (int i = 1; i <= k; i++) {
            dp[0][2*i - 1] = -prices[0];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= 2*k; j++) {
                if (j % 2 == 0){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1] + prices[i]);
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1] - prices[i]);
                }
            }
        }
        return dp[len-1][2*k];
    }

}
